#include <string.h>
#include <stdlib.h>
#include <time.h>

// 交换指针指向的元素值（pa 和 pb为 char* 类型）
#define SWAP(pa, pb, size)          \
    do{                             \
        char *tmp = malloc((size)); \
        memcpy(tmp, (pa), (size));  \
        memcpy((pa), (pb), (size)); \
        memcpy((pb), tmp, (size));  \
        free(tmp);                  \
        tmp = NULL;                 \
    } while(0)


void quick_sort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) 
{
    if (nmemb < 2) // 递归终止条件，只有一个元素
        return;

    // void指针没有运算能力，将void指针转换为char指针，便于按字节访问数组元素
    char *arr = (char *)base;
    char *pivot = NULL; // 定义一个指向基准值（第一个元素）的指针
    size_t left, right; // 定义左右两个“哨兵”

    pivot = malloc(size);
    if (pivot == NULL)
        return;
    memcpy(pivot, base, size); // 内存拷贝保存基准值

    left = 0;
    right = nmemb - 1;
    while (left < right) {
        while (left < right && compar(arr + size * right, pivot) >= 0)
            right--; // 从右往左找第一个比基准值小（或大）的数据
        memcpy(arr + size * left, arr + size * right, size); // 数据赋值

        while (left < right && compar(arr + size * left, pivot) <= 0)
            left++; // 从左往右找第一个比基准值大（或小）的数据
        memcpy(arr + size * right, arr + size * left, size); // 数据赋值
    }
    memcpy(arr + size * left, pivot, size); // 最后的位置就是基准值的位置(此时left和right相同)

    free(pivot); // 释放申请的空间，防止内存泄露
    pivot = NULL;

    quick_sort(arr, left, size, compar); // 递归排序左区间
    quick_sort(arr + (left + 1) * size, nmemb - left - 1, size, compar); // 递归排序右区间
}

void quick_sort_optimize(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) 
{
    if (nmemb < 2) // 递归终止条件，只有一个元素
        return;

    // void指针没有运算能力，将void指针转换为char指针，便于按字节访问数组元素
    char *arr = (char *) base;
    char *pivot = NULL; // 定义一个指向基准值（第一个元素）的指针
    size_t left, right, i; // 定义三个“哨兵”

    // 随机选取基准值
    srand(time(NULL)); // 初始化随机数种子
    size_t pivot_index = rand() % nmemb; // 生成随机索引
    pivot = malloc(size);
    if (pivot == NULL)
        return;

    // 将随机选取的基准值与第一个元素交换
    memcpy(pivot, arr + size * pivot_index, size); // 保存随机基准值
    SWAP(arr + size * pivot_index, arr, size); // 元素交换

    // 三路快排
    left = 0;
    right = nmemb - 1;
    i = 1;
    while (i <= right) {
        if (compar(pivot, arr + size * i) > 0) {
            SWAP(arr + size * i, arr + size * left, size);
            left++;
            i++;
        } else if (compar(pivot, arr + size * i) < 0) {
            SWAP(arr + size * i, arr + size * right, size);
            right--;
        } else {
            i++;
        }
    }

    free(pivot); // 释放申请的空间，防止内存泄露
    pivot = NULL;

    quick_sort(arr, left, size, compar); // 递归排序左区间
    quick_sort(arr + (right + 1) * size, nmemb - right - 1, size, compar); // 递归排序右区间
}



